#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int maxProfit(vector<int>& prices)
    {
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;

        for (size_t i = 1; i < prices.size(); ++i)
        {
            buy1 = std::max(buy1, -prices[i]);
            sell1 = std::max(sell1, buy1 + prices[i]);
            buy2 = std::max(buy2, sell1 - prices[i]);
            sell2 = std::max(sell2, buy2 + prices[i]);
        }

        return sell2;
    }
};

//class Solution {
//public:
//    int maxProfit(vector<int>& prices)
//    {
//        if (prices.size() == 1)
//        {
//            return 0;
//        }
//
//        int f0 = -prices[0];
//        int f1 = -1000000, f2 = -1000000, f3 = -1000000;
//
//        for (size_t i = 1; i < prices.size(); ++i)
//        {
//            int newf0 = std::max(f0, -prices[i]);
//            int newf1 = std::max(f2 - prices[i], f1);
//            int newf2 = std::max(f0 + prices[i], f2);
//            int newf3 = std::max(f3, f1 + prices[i]);
//
//            f0 = newf0;
//            f1 = newf1;
//            f2 = newf2;
//            f3 = newf3;
//
//            //printf("(%d) f0:%d, f1:%d, f2:%d, f3:%d\n", i + 1, f0, f1, f2, f3);
//        }
//
//        return std::max(std::max(f2, f3), 0);
//
//    }
//};